package www.com.star;

import javax.xml.soap.DetailEntry;
import java.awt.*;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.CountDownLatch;
import java.util.regex.Pattern;

/**
 *  链表：
 *      优点： 删除快、插入快  时间复杂度 O(1)
 *      缺点： 查询慢  时间复杂度 O(n)
 * 双向循环链表
 *    与单链表比较 ：    1.能更快的找到前一节点   2.能更快的找到尾节点
 *    与单循环链表比较： 1.能更块的找到前一节点
 *    与双向链表比较：   1.能更快的找到尾节点
 */
public class Linkedlist {
    /**
     * 节点类
     */
    class Node{
        private Integer num;
        private Node preNode;
        private Node nextNode;

        @Override
        public String toString() {
            return "Node{" +
                    "num=" + num +
                    '}';
        }
    }
    //头结点
    private Node head;
    private Integer count;

    /**
     * 尾部添加  时间复杂度 O(1)
     * @param num
     * @return
     */
    public Node add(Integer num){
        Node node = new Node();
        node.num = num;
        if (count == null){
            head = new Node();
            //赋值  先配两边、后配中间
            head.nextNode = node; //  head -> node
            head.preNode = node;  //  head <- node
            node.preNode = head;  //  node <- head
            node.nextNode = head; //  node -> head
            //计数
            count = 1;
            return node;
        }
        // p 为前节点
        Node p = head.preNode;
        //赋值
        p.nextNode = node;  // p -> node
        head.preNode = node;    // head <- node
        node.preNode = p;   // node <- p
        node.nextNode = head;   // node -> head
        count++;//计数
        //返回当前节点
        return node;
    }

    /**
     * 删除给定值，并返回该节点  null 为删除失败，节点不存在
     *  时间复杂度 O(1)
     * @param num
     * @return
     */
    public Node remove(Integer num){
        Node node = findByNum(num);
        if (node == null){
            return null;
        }
        Node p = node.preNode;//获取前节点
        Node q = node.nextNode;//获取后节点
        //如果删除的节点为尾节点 则 修改为结尾 前一节点
        if (node.equals(head.preNode)){
            head.preNode = p;
        }
        p.nextNode = q;  // p -> q
        q.preNode = p;   // q <- p
        count--;
        return  node;
    }

    /**
     * 根据指定值查询,并返回该节点   null 为不存在
     *   时间复杂度 O(n)
     * @param num
     * @return
     */
    public Node findByNum(Integer num){
        if (count == null){
            System.out.println("查询链表为空！");
            return null;
        }
        Node q = head.nextNode;
        while (!q.equals(head)){
            if (q.num.equals(num)){
                return q;
            }
            q = q.nextNode;
        }
        System.out.println("未找到匹配数");
        return  null;
    }

    /**
     * 展示当前链表数据
     */
    public void show(){
        if (count == null){
            System.out.println("链表为空");
            return ;
        }
        Node q = head.nextNode;
        while(!q.equals(head)){
            System.out.print(q.num+",");
            q = q.nextNode;
        }
    }
}
